P1891 疯狂LCM

发布于 2020-09-12 | 分类于数论 | 4分钟 | 516字数 | 浏览量：

\sum_{i=1}^n lcm(i,n)

\sum_{i=1}^n \frac{i*n}{gcd(i,n)}

n\sum_{i=1}^n \frac{i}{gcd(i,n)}

n\sum_{d|n}\sum_{i=1}^n [gcd(i,n)=d]\frac{i}{d}

n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}} [gcd(i,\frac{n}{d})=1]i

n\sum_{d|n}\sum_{i=1}^{d} [gcd(i,d)=1]i

令 $f(n)=\sum_{i=1}^ni[gcd(i,n)=1] , g(n)=\sum_{i|n} f(i)$

f(n)=\frac{1}{2} \sum_{i=1}^n i[gcd(i,n)=1]+(n-i)[gcd(n-i,n)=1]

=\frac{1}{2} \sum_{i=1}^n n[gcd(i,n)=1]

=\frac{n}{2} \sum_{i=1}^n [gcd(i,n)=1]

=\frac{n \times \varphi(n)}{2}

枚举因数预处理 $g(n)$ ，注意一下 $f(1)=1$ 。

答案为： $n \times g(n)$

#include <cstdio>

const int MAXN = 1000000;
int t , n , k , prime[ MAXN + 5 ] , phi[ MAXN + 5 ];
long long g[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
	phi[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			phi[ i ] = i - 1;
		}
		for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) {
				phi[ i * prime[ j ] ] = phi[ i ] * prime[ j ];
				break;
			}
			phi[ i * prime[ j ] ] = phi[ i ] * ( prime[ j ] - 1 );
		}
	}

	for( int i = 1 ; i <= MAXN ; i ++ )
		for( int j = i ; j <= MAXN ; j += i )
			g[ j ] += i == 1 ? 1 : 1ll * phi[ i ] * i / 2;
}

int main( ) {
	sieve( );
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d",&n);
		printf("%lld\n", n * g[ n ] );
	}
	return 0;
}

P1891 疯狂LCM

感谢您的支持，我会继续努力的!